package com.beney.ds.sorting;

import com.beney.ds.sorting.abs.AbstractSort;

public class QuickSort extends AbstractSort {
    private QuickSort() {
    }

    public static void sort(Comparable[] a) {
        if (a == null) return;
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        int k = partition(a, lo, hi, mid);
        sort(a, lo, k - 1);
        sort(a, k + 1, hi);
    }

    /**
     * @return 按照轴值划分完后，轴值的位置
     */
    private static int partition(Comparable[] a, int lo, int hi, int p) {
        int k = lo;
        Comparable pivot = a[p];
        swap(a, p, hi);
        for (int i = lo; i < hi; ++i) {
            if (a[i].compareTo(pivot) < 0) {
                swap(a, k++, i);
            }
        }
        swap(a, k, hi);
        return k;
    }
}
